在 C++ 中，管理容器的增長是一場在以下兩者之間的建築性協調 大小 （目前元素）和 容量 （預留記憶體）。對於連續容器如 vector 以及 string，達到容量時會觸發 重新配置：系統會尋找更大的記憶體區塊，將所有元素移動至新區塊，並銷毀舊區塊。這是一個耗時的 $O(n)$ 操作，會導致 迭代器失效——你對舊元素的指標會變成「懸空」且危險。
1. 擴展策略
為避免頻繁的重新配置， vector 實作會分配「緩衝」空間。使用 c.reserve(n) 指令可明確設定最小容量而不新增元素，而 c.shrink_to_fit() 則是向作業系統請求釋放多餘記憶體的非強制性要求。
2. resize 與 reserve 的差異
雖然 reserve 僅影響緩衝區， resize(n) 卻會主動改變容器的邏輯。透過 resize 縮小會刪除元素，而擴展則會加入預設初始化的值。
⚠️ 警告： 如果
resize 縮小容器，指向被刪除元素的迭代器會失效。若擴展導致重新配置， 所有 所有迭代器都會失效。main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
Exercise 9.34: Predict the behavior of this loop: while (iter != vi.end()) { if (*iter % 2) iter = vi.insert(iter, *iter); ++iter; }
It duplicates all odd numbers once and finishes.
It results in an infinite loop if an odd number is found.
It skips all odd numbers.
It causes a compilation error because of iterator types.
✅ Correct!
This is an infinite loop. vi.insert(iter, *iter) inserts before the current element and returns an iterator to the NEW element. The ++iter then moves back to the original odd element, repeating the process forever.❌ Incorrect
Analyze the return value of insert: it points to the newly inserted element. Incrementing once just puts you back on the original element you just processed.QUESTION 2
Exercise 10.10: Why don't generic algorithms like find or sort change the size of containers?
They operate on iterators, which provide no interface to add/remove container memory.
Changing size would be too slow for generic code.
The C++ standard forbids algorithms from using memory.
Algorithms only work on fixed-size arrays.
✅ Correct!
Algorithms are decoupled from containers. They only see iterators and can only modify the values the iterators point to; they cannot call container-specific members like push_back or erase.❌ Incorrect
Recall the 'Iterator Bridge' concept: algorithms use iterators to remain container-agnostic.QUESTION 3
Given vec has 25 elements, what happens if we call vec.resize(100) then vec.resize(10)?
Size becomes 100, then drops to 10; capacity likely stays at 100 throughout.
Size becomes 100, then 10; capacity drops to 10 immediately.
The program crashes on the second resize.
The elements from index 10-99 are moved to a temporary buffer.
✅ Correct!
resize(100) adds 75 default-initialized elements. resize(10) destroys the last 90 elements, but the allocated capacity remains 100 unless shrink_to_fit is called.❌ Incorrect
Resize shrinks the 'size', but capacity does not shrink automatically to save performance.QUESTION 4
What restriction is placed on the element type when calling the single-argument version of resize?
It must be a primitive type (int, double, etc.).
It must have a default constructor.
It must have a copy constructor.
It cannot be a const type.
✅ Correct!
Since resize(n) creates new elements to reach size n, those elements must be initialized using a default constructor.❌ Incorrect
If we don't provide an initial value, the container must know how to build a 'default' one.QUESTION 5
Exercise 10.39: What kind of iterator does a list have versus a vector?
List: Forward; Vector: Random-access
List: Bidirectional; Vector: Random-access
Both have Random-access iterators.
List: Output; Vector: Input
✅ Correct!
std::list is a doubly-linked list supporting bidirectional movement. std::vector is an array supporting pointer-like arithmetic (Random-access).❌ Incorrect
Can you do 'it + 5' on a list? No, which means it isn't random-access.Case Study: Safe Iterator Loops
Managing Growth in Real-time Applications
You are processing a vector of integers. For every odd number, you must duplicate it. You also need to maintain efficiency and avoid segmentation faults caused by container reallocation during the loop.
Q
1. Re-implement Exercise 9.34 correctly to avoid the infinite loop and handle iterator invalidation.
Solution:
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
Q
2. Rewrite the duplicate word elimination logic from § 10.2.3 to use a list instead of a vector. What changes?
Solution:
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Q
3. Exercise 10.19: Rewrite the biggies logic to use stable_partition instead of find_if to maintain original order.
Solution:
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.